<?php
/*
 * Created on 30.12.2005
 * Parser Engine for ppage LALR(1) parser generator tables
 */

/***************************************************************
*  Copyright notice
*
*  (c) 2005-2006 Marcel Linnenfelser (m.linnen@synflag.de)
*  All rights reserved
*
*  This script is part of the ppage project. The ppage project is
*  free software; you can redistribute and/or modify this file 
*  under the terms of the GNU Lesser General Public License as 
*  published by the Free Software Foundation; either version 2 of 
*  the License, or (at your option) any later version.
*
*  The GNU Lesser General Public License can be found at
*  http://www.gnu.org/licenses/lgpl.html.
*  A copy is found in the textfile LGPL.txt.
*
*
*  This script is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  This copyright notice MUST APPEAR in all copies of the script!
***************************************************************/


define("PPAGE_ERROR_WRONG_TOKEN", 1);
define("PPAGE_ERROR_NO_NEXT_TOKEN", 2);
define("PPAGE_ERROR_GOTO_TABLE_ERROR", 3);

/**
 * Parser stack machine for evaluation of the parser table and creating AST
 */
class phpinchains_parser_ParserMachine
{

    var $table;
    var $stack;
    var $error;
    
    function __construct ($lexer, $table, $productions, $translations, $verbose = false, $quiet = false)
    {
        if (!count($table) || !count($productions))
            die ("PARSER ERROR: empty parsertable");
        $this->lexer = $lexer;
        $this->table = $table;
        $this->productions = $productions;
        $this->stack = array(0);
        $this->verbose = $verbose;
        $this->quiet   = $quiet;
        $this->translations = $translations;
        if ($this->verbose)
        for ($i = 0; $i < count($productions); $i++)
        {
            print $i.": ".$productions[$i][0]." ::= ".join(" ", $productions[$i][1])."\n";
        }
    }
    
    function top()
    {
        return $this->stack[count($this->stack)-1];
    }
    
    function translateTokens ($ids) {
        $possibleTokens = array();
        foreach ($ids as $t) {
            if ($this->translations[$t])
                $possibleTokens[] = $this->translations[$t];
        }
        return $possibleTokens;
    }
    
    /**
     * Called for parser run
     * 
     * If parsing is successful, true is returned else false.
     */
    function run (& $callback)
    {
        $token = array();
        $token = $this->lexer->nextToken();
        $callback->shift($token, $this->stack);
        $action = -2;
        $treestack = array();
        $tree    = array('S\'', array());
        $current = & $tree;
        while ($action[0] != 'a') // a ^= acc
        {
            if (!($action = $this->table[$this->top()][$token['type']]))
            {
                if ($this->quiet) 
                {
                    $token['cause']           = PPAGE_ERROR_WRONG_TOKEN;
                    $token['possible_tokens'] = array_keys($this->table[$this->top()]);
                    $this->error = $token;
                } 
                else {
                    print ("<b>Parsing error:</b> at token $token[value] of $token[type] at $token[line]:$token[charno]; possible tokens are ".join(", ", $this->translateTokens(array_keys($this->table[$this->top()])))." <br/>\n");
                }
                return false;
            }
            if ($action[0] == 's') // s ^= shift
            {
                $step = $action[1];
                if ($this->verbose)
                {
                    print "shift $token[value], ";
                    print "push $token[value] ";
                }
                $current[1][] = $token;
                $this->stack[] = $token['type'];
                if ($this->verbose)
                    print "push $step\n";
                $this->stack[] = $step;
                if ($this->lexer->hasNextToken())
                    $token = $this->lexer->nextToken();
                else
                {
                    if ($this->quiet) 
                    {
                        $token['cause']           = PPAGE_ERROR_NO_NEXT_TOKEN;
                        $this->error = $token;
                    }
                    else
                        print ("<b>Parsing error:</b> no next token<br/>");
                    return false;
                }
                $callback->shift($token, $this->stack);
            }
            elseif ($action[0] == 'r') // r ^= reduce
            {
                $rule = $action[1];
                if ($this->verbose)
                    print "$token[type] reduce $rule, ";
                for ($i = 0; $i < count($this->productions[$rule][1]); $i++)
                {
                    if ($this->verbose)
                        print "poppop ";
                    array_pop($this->stack);
                    $tokenname = array_pop($this->stack);
                }
                $callback->reduce($rule, $this->productions[$rule], $this->stack);
                if (!($goto = $this->table[$this->top()][$this->productions[$rule][0]]))
                {
                    if ($this->quiet) 
                    {
                        $token                    = $this->productions[(int)$rule];
                        $token['cause']           = PPAGE_ERROR_GOTO_TABLE_ERROR;
                        $this->error = $token;
                    }
                    else
                        print ("<b>Parsing error:</b> table error no goto for token ".$this->productions[(int)$rule][0]."<br/>\n");
                    return false;
                }
                if ($this->verbose)
                    print "goto for ".$this->productions[$rule][0]." is $goto\n";
                $this->stack[] = $this->productions[$rule][0];
                $this->stack[] = $goto;
            }
            if ($this->verbose)
                print "stack: ".join(" ", $this->stack)."\n";
        }
        $callback->reduce(0, $this->productions[0], $this->stack);
        return true;
    }
    
    /**
     * Returns the error array which is collected in quiet mode
     * 
     * 'cause' is one of the 3 constants defined at the beginning of this file.
     * If 'cause' is PPAGE_ERROR_WRONG_TOKEN then key 'possible_tokens' exists
     * and contains an array of possible tokens. It has to be decoded with the 
     * mapping in the grammar table file.
     */
    function getError() 
    {
        return $this->error;
    }

}

